Since the Bin Packing Problem (BPP) is one of the main NP-hard problems, alot of approximation algorithms have been suggested for it. It has been proventhat the best algorithm for BPP has the approximation ratio of 3/2 and the timeorder of O(n), unless P=NP. In the current paper, a linear 3/2-approximationalgorithm is presented. The suggested algorithm not only has the best possibletheoretical factors, approximation ratio, space order, and time order, but alsooutperforms the other approximation algorithms according to the experimentalresults, therefore, we are able to draw the conclusion that the algorithms isthe best approximation algorithm which has been presented for the problem untilnow. Key words: Approximation Algorithm, Bin Packing Problem, ApproximationRatio, NP-hard.
展开▼
